package externalSort.Tournament;

// 一定要保证是 完全二 叉树！！！！！！

public class tournamentTree {
    private final int k; // 路数
    private final int size; // 数组大小
    private final Node[] nodes; // 静态数组存储所有节点
    private final int[] leaves; // 叶子节点在数组中的索引
    private int[] loser;

    public tournamentTree(int k) {
        this.k = k;
        this.size = 2 * k - 1; // 完全二 叉树的节点总数
        this.nodes = new Node[size];
        this.leaves = new int[k];

        initializeTree();
    }

    public void initVals(int[] initialValues){
        // 设置所有叶子节点的初始值
        for (int way = 0; way < k; way++) {
            int leafIndex = leaves[way];
            nodes[leafIndex].val = way<initialValues.length?initialValues[way]:Integer.MAX_VALUE;
            nodes[leafIndex].term = 0; //初始化的轮次为0
            loser[leafIndex]=leafIndex;//失败者就是自己
        }

        // 构建初始的败者树
        initAdjust();
    }

    public void initVals(){
        // 设置所有叶子节点的初始值
        for (int way = 0; way < k; way++) {
            int leafIndex = leaves[way];
            loser[leafIndex]=leafIndex;//失败者就是自己
        }

        // 构建初始的败者树
        initAdjust();
    }

    private void initAdjust() {
        for(int i=k-2;i>=0;i--){
            int leftChildIdx=this.getLeftChildIndex(i),rightChildIdx=this.getRightChildIndex(i);
            if(compare(loser[leftChildIdx],loser[rightChildIdx])){//留左侧
                setValue(nodes[i],nodes[loser[leftChildIdx]]);
                loser[i]=loser[rightChildIdx];
            }else{
                setValue(nodes[i],nodes[loser[rightChildIdx]]);
                loser[i]=loser[leftChildIdx];
            }
        }
    }

    // 初始化败者树
    private void initializeTree() {
        // 初始化所有节点
        for (int i = 0; i < size; i++) {
            nodes[i] = new Node(Integer.MIN_VALUE ,-1);
        }

        // 设置叶子节点
        for (int i = 0; i < k; i++) {
            int leafIndex = k - 1 + i;
            nodes[leafIndex].isLeaf = true;
            nodes[leafIndex].way = i; // 记录路数
            leaves[i] = leafIndex;
        }

        loser=new int [size];

        initVals();

        System.out.println("败者树初始化完成，初始胜者: " + getLoser().val + " (路数: " + getLoserWay() + ")");
    }

    // 比较两个元素
    private boolean compare(int index1, int index2) {
        Node node1 = nodes[index1];
        Node node2 = nodes[index2];

        if (node1.term > node2.term) {
            return true; // 轮次大的获胜，留在原地
        }
        return node1.term==node2.term && node1.val >= node2.val; // term相同时，值小的胜出（用于升序排序）
    }

    // 获取父节点索引
    private int getParentIndex(int index) {
        if (index == 0) return -1; // 根节点没有父节点
        return (index - 1) / 2;
    }

    // 获取左孩子索引
    private int getLeftChildIndex(int index) {
        int left = 2 * index + 1;
        return left < size ? left : -1;
    }

    // 获取右孩子索引
    private int getRightChildIndex(int index) {
        int right = 2 * index + 2;
        return right < size ? right : -1;
    }

    private int getSiblingsIndex(int index){
        if(index==0){
            System.out.println("[externalSort.tournamentTree.getSiblingsIndex]:试图查询头结点的兄弟");
            return -1;
        }
        int parent=getParentIndex(index);
        int left=getLeftChildIndex(parent);
        int right=getRightChildIndex(parent);
        return (index==left)?right:left;
    }


    public void setValue(Node cur,Node newNode){
        cur.val=newNode.val;
        cur.way=newNode.way;
        cur.term=newNode.term;
    }

    // 向上调整
    // 这里应该是调整过叶子节点的loser
    private void adjustUpward(int index) {
        int current = index;

        while (current > 0) {
            int parent = getParentIndex(current);

//            System.out.println(nodes[loser[current]].val+" "+nodes[parent].val);

            if(compare(loser[current],parent)){// 当前节点获胜，留在原地
                setValue(nodes[parent],nodes[loser[current]]);
                /*
                再考虑一个问题，如果当前的父亲节点要继续往上传，那这个父亲节点是从哪里来的呢
                肯定是兄弟节点的loser
                 */
                loser[parent]=loser[getSiblingsIndex(current)];
            }else{//否则继续上传
                loser[parent]=loser[current];
            }
            current=parent;
        }
    }

    // 获取最大失败者（根节点）
    public Node getLoser() {
        return nodes[loser[0]];
    }


    public void printTree() {
        System.out.println("Tournament Tree Structure:");
        for (int i = 0; i < size; i++) {
            Node node = nodes[i];
            String type = node.isLeaf ? "Leaf" : "Internal";
            System.out.printf("Index %d: val=%d, term=%d, way=%d, %s%n",
                    i, node.val, node.term, node.way, type);
        }
    }

    // 汰换操作 ：返回被汰换的节点值，同时进行插入
    public int moveOut(int newValue,boolean ifFinished) {

        int ret=getLoser().val;
        /*
        想这样的一个问题，你什么时候需要term+=1?
        肯定是说如果当前你想加入的节点比你当前汰换出去的节点的值来的小
        这时你迫不得已必须得另起炉灶了
         */
        int idx=leaves[getLoserWay()];
        // 那啥时候isFinished==true呢，肯定是最后结束要清场排空了
        if(ifFinished){
            nodes[idx].term=Integer.MAX_VALUE;
        }
        else if(ret==Integer.MIN_VALUE){ // 初始情况
            nodes[idx].term=1;
        }
        else if(ret>newValue) { // 新串
            nodes[idx].term++;
        }

        nodes[idx].val=newValue;

        // 开始下一轮的汰换
        loser[idx]=idx;
        adjustUpward(idx);

//        this.printTree();

        return ret;
    }

    // 获取胜者所在的路数 - 用于外部排序中确定从哪路读取下一个元素
    public int getLoserWay() {
        return getLoser().way;
    }
}
